import java.util.*;

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        System.out.println(lists);
    }
}

//双指针，官方题解，时间复杂度O(n^2)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> ret = new ArrayList<>();

        int prevA = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int a = nums[i];
            if (prevA == a) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;

            int prevB = Integer.MAX_VALUE;
            int k = nums.length - 1;
            for (int j = i + 1; j < nums.length - 1; j++) {
                int b = nums[j];
                if (prevB == b) continue;
                if (nums[i] + nums[j] + nums[j + 1] > 0) break;

                int expectedC = -a - b;
                while (j < k && nums[k] > expectedC) k--;
                if (j == k) break;
                if (nums[k] == expectedC) ret.add(Arrays.asList(a, b, expectedC));

                prevB = b;
            }

            prevA = a;
        }

        return ret;
    }
}


class Solution2 {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> ret = new ArrayList<>();

        int prevA = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int a = nums[i];
            if (prevA == a) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;

            int prevB = Integer.MAX_VALUE;
            for (int j = i + 1; j < nums.length - 1; j++) {
                int b = nums[j];
                if (prevB == b) continue;
                if (nums[i] + nums[j] + nums[j + 1] > 0) break;

                int expectedC = -a - b;
                if (find(nums, expectedC, j + 1) >= 0) {
                    ret.add(Arrays.asList(a, b, expectedC));
                }

                prevB = b;
            }

            prevA = a;
        }

        return ret;
    }


    int find(int[] a, int value, int start) {
        return _find(a, value, start, a.length - 1);
    }

    int _find(int[] a, int value, int l, int h) {
        if (l > h) return -1;
        int k = (l + h) / 2;
        if (a[k] < value) return _find(a, value, k + 1, h);
        if (a[k] > value) return _find(a, value, l, k - 1);
        return k;
    }
}